package leetcode.tree_problem;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 662. 二叉树最大宽度
 * https://leetcode-cn.com/problems/maximum-width-of-binary-tree/
 */
public class 二叉树最大宽度 {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null){
            return 0;
        }
        int maxLength = 0;
        Deque<TreeNodeWithNum> deque = new LinkedList<>();
        deque.offer(new TreeNodeWithNum(root , 1));

        while (!deque.isEmpty()){
            int curWidth = 0;//层宽
            int curDequeSize = deque.size();//但前层存的元素个数

            int numLeft = 0;//左编号
            int numRight = 0;//右编号

            for (int i = 0; i < curDequeSize; i++) {//队列元素长
                TreeNodeWithNum curNode = deque.poll();

                if (i == 0){
                    numLeft = curNode.num;
                }
                if (i == curDequeSize - 1){
                    numRight = curNode.num;
                }
                if (curNode.root.left != null){//这里主要是要把左树与右树继续入队作为下层要取处理的东西
                    deque.offer(new TreeNodeWithNum(curNode.root.left , 2 * curNode.num));//这步真的很妙很妙
                    //这里注意节点是谁，是当前正在处理的curNode.root，root是根
                }
                if (curNode.root.right != null){
                    deque.offer(new TreeNodeWithNum(curNode.root.right , 2 * curNode.num + 1));
                }
                curWidth = numRight - numLeft + 1;
            }
            maxLength = Math.max(maxLength , curWidth);
        }

        return maxLength;
    }
    public class TreeNodeWithNum{
        TreeNode root;
        int num;

        public TreeNodeWithNum(TreeNode root, int num) {
            this.root = root;
            this.num = num;
        }
    }
}
